package de.pass.ch.datastr;

import java.awt.IllegalComponentStateException;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Iterator;

import de.pass.ch.graph.edge.CompleteEdge;

/**
 * Doppelt verkettete Liste fuer die Klasse {@link CompleteEdge}. Diese Liste
 * wird zum Einlesen eines Graphs verwendet.
 * 
 * @author Maximilian Schmitt
 * 
 */
public class EdgeList implements Iterable<CompleteEdge> {

	/**
	 * head-Element der Liste
	 */
	private CompleteEdge head;

	/**
	 * tail-Element der Liste
	 */
	private CompleteEdge tail;

	/**
	 * Anzahl der Elemente in der Liste
	 */
	private int size;

	/**
	 * Konstruktor der EdgeList. Erstellt eine leere Liste.
	 */
	public EdgeList() {
		head = null;
		tail = null;
		size = 0;
	}

	/**
	 * Fuegt die gegebene {@link CompleteEdge} e ans Ende der Liste ein.
	 * 
	 * @param e
	 *            - einzufuegende {@link CompleteEdge}
	 * @return true, wenn das Einfuegen erfolgreich war
	 */
	public boolean add(CompleteEdge e) {

		if (size == 0) {

			head = tail = e;
			e.setPrevious(null);
			e.setNext(null);

		} else {

			tail.setNext(e);
			e.setPrevious(tail);
			e.setNext(null);
			tail = e;

		}

		size++;
		return true;
	}

	/**
	 * Fuegt die gegebene {@link CompleteEdge} {@code e} am gegebenen Index
	 * {@code index} der Liste ein.
	 * 
	 * @param e
	 *            - einzufuegende {@link CompleteEdge}
	 * @param index
	 *            - Index, an der die {@link CompleteEdge} eingefuegt werden
	 *            soll
	 * @return true, wenn das Einfuegen erfolgreich war
	 */
	public boolean add(CompleteEdge e, int index) {

		if (index < 0 || index > size) {
			return false;
		}

		if (index == 0 && index == size) {

			head = tail = e;
			e.setPrevious(null);
			e.setNext(null);

		} else if (index == 0) {

			head.setPrevious(e);
			e.setNext(head);
			e.setPrevious(null);
			head = e;

		} else if (index == size) {

			return add(e);

		} else {

			CompleteEdge tmp = get(index);
			e.setNext(tmp);
			e.setPrevious(tmp.getPrevious());
			tmp.getPrevious().setNext(e);
			tmp.setPrevious(e);

		}

		size++;
		return true;

	}

	/**
	 * Gibt an, ob die gegebene {@link CompleteEdge} {@code e} in der Liste ist.
	 * 
	 * @param e
	 *            - {@link CompleteEdge}, nach der in der Liste gesucht wird
	 * @return true, wenn {@code e} in der Liste ist
	 */
	public boolean contains(CompleteEdge e) {
		for (CompleteEdge tmp = head; tmp != null; tmp = tmp.getNext()) {
			if (e.equals(tmp))
				return true;
		}
		return false;
	}

	/**
	 * Liefert die {@link CompleteEdge} mit Index {@code index}.
	 * 
	 * @param index
	 *            - Index der gesuchten {@link CompleteEdge}
	 * @return {@link CompleteEdge} an Index {@code index}
	 */
	public CompleteEdge get(int index) {
		if (index < 0 || index >= size) {
			throw new IndexOutOfBoundsException("Index: " + index + ", Size: "
					+ size);
		}

		if (index > (size >> 1)) {
			int position = size - 1;
			CompleteEdge e = tail;

			while (position > index) {
				e = e.getPrevious();
				position--;
			}

			return e;
		} else {
			int position = 0;
			CompleteEdge e = head;

			while (position < index) {
				e = e.getNext();
				position++;
			}

			return e;
		}
	}

	/**
	 * Entfernt die gegebene {@link CompleteEdge} {@code e} aus der Liste.
	 * 
	 * @param edge
	 *            - zu entfernende {@link CompleteEdge}
	 */
	public void remove(CompleteEdge edge) {

		CompleteEdge p, n;
		p = edge.getPrevious();
		n = edge.getNext();

		if (p == null && n == null) {
			head = tail = null;
		} else if (p == null) {
			head = n;
			head.setPrevious(null);
		} else if (n == null) {
			tail = p;
			tail.setNext(null);
		} else {
			p.setNext(n);
			n.setPrevious(p);
		}

		size--;

	}

	/**
	 * Entfernt die {@link CompleteEdge} an der Stelle {@code index} aus der
	 * Liste.
	 * 
	 * @param index
	 *            - Index der {@link CompleteEdge}, die entfernt werden soll
	 */
	public void remove(int index) {

		if (index < 0 || index >= size) {
			return;
		}

		CompleteEdge e, p, n;
		e = get(index);
		p = e.getPrevious();
		n = e.getNext();

		if (p == null && n == null) {
			head = tail = null;
		} else if (p == null) {
			head = n;
			head.setPrevious(null);
		} else if (n == null) {
			tail = p;
			tail.setNext(null);
		} else {
			p.setNext(n);
			n.setPrevious(p);
		}

		size--;

	}

	/**
	 * Liefert die Anzahl der Listen-Elemente.
	 * 
	 * @return Anzahl der Elemente in der Liste.
	 */
	public int size() {
		return size;
	}

	/**
	 * Sortiert die Liste im Intervall [{@code fromIdx}, {@code toIdx}[.
	 * 
	 * @param fromIdx
	 * @param toIdx
	 */
	public void sort(int fromIdx, int toIdx) {
		if (fromIdx < 0 || fromIdx >= size || toIdx < 0 || toIdx > size
				|| fromIdx >= toIdx) {

			System.out.println("Ung\u00fcltige Indizes!");

		} else {

			Runtime r = Runtime.getRuntime();
			int range = toIdx - fromIdx;
			// System.out.println("free Memory: "
			// + (r.freeMemory() + r.maxMemory() - r.totalMemory()));
			if (range * 64 < (r.freeMemory() + r.maxMemory() - r.totalMemory())) {
				arraySort(fromIdx, toIdx);
			} else {
				System.out.println("InsertionSort, da " + (range * 64)
						+ " byte ben\u00f6tigt und nur "
						+ (r.freeMemory() + r.maxMemory() - r.totalMemory())
						+ " byte frei");
				insertionSort(fromIdx, toIdx);
			}
		}
	}

	/**
	 * Sortiert die Liste im Intervall [{@code fromIdx}, {@code toIdx}[ mit dem
	 * gegebenen {@link Comparator}.
	 * 
	 * @param fromIdx
	 * @param toIdx
	 * @param comp
	 */
	public void sort(int fromIdx, int toIdx, Comparator<CompleteEdge> comp) {
		if (fromIdx < 0 || fromIdx >= size || toIdx < 0 || toIdx > size
				|| fromIdx >= toIdx) {

			System.out.println("Ung\u00fcltige Indizes!");

		} else {

			Runtime r = Runtime.getRuntime();
			// int range = toIdx - fromIdx;
			System.gc();
			System.out.println("free Memory: "
					+ (r.freeMemory() + r.maxMemory() - r.totalMemory()));
			// if (range * 64 < (r.freeMemory() + r.maxMemory() -
			// r.totalMemory())) {
			arraySort(fromIdx, toIdx, comp);
			// } else {
			// System.out.println("InsertionSort, da " + (range * 64)
			// + " byte ben\u00f6tigt und nur "
			// + (r.freeMemory() + r.maxMemory() - r.totalMemory())
			// + " byte frei");
			// insertionSort(fromIdx, toIdx, comp);
			// }
			System.gc();
		}
	}

	/**
	 * Vertauscht die CompleteEdges an Index {@code edge1} und {@code edge2}
	 * miteinander in der Liste.
	 * 
	 * @param edge1
	 * @param edge2
	 * @return
	 */
	public boolean swap(int edge1, int edge2) {

		if (edge1 < 0 || edge1 >= size) {
			return false;
		}

		if (edge2 < 0 || edge2 >= size) {
			return false;
		}

		if (edge1 == edge2)
			return true;

		if (Math.abs(edge2 - edge1) == 1) {

			CompleteEdge tmp1, tmp2;

			tmp1 = edge1 < edge2 ? get(edge1) : get(edge2);
			tmp2 = edge1 < edge2 ? get(edge2) : get(edge1);

			CompleteEdge p = tmp1.getPrevious();
			CompleteEdge n = tmp2.getNext();

			tmp1.setPrevious(tmp2);
			tmp1.setNext(n);
			tmp2.setPrevious(p);
			tmp2.setNext(tmp1);

			if (p == null) {
				head = tmp2;
			} else {
				p.setNext(tmp2);
			}

			if (n == null) {
				tail = tmp1;
			} else {
				n.setPrevious(tmp1);
			}

		} else {

			CompleteEdge tmp1 = get(edge1);
			CompleteEdge p1 = tmp1.getPrevious();
			CompleteEdge n1 = tmp1.getNext();

			CompleteEdge tmp2 = get(edge2);
			CompleteEdge p2 = tmp2.getPrevious();
			CompleteEdge n2 = tmp2.getNext();

			tmp1.setPrevious(p2);
			tmp1.setNext(n2);
			tmp2.setPrevious(p1);
			tmp2.setNext(n1);

			if (p1 == null) {
				head = tmp2;
			} else {
				p1.setNext(tmp2);
			}

			if (n1 == null) {
				tail = tmp2;
			} else {
				n1.setPrevious(tmp2);
			}

			if (p2 == null) {
				head = tmp1;
			} else {
				p2.setNext(tmp1);
			}

			if (n2 == null) {
				tail = tmp1;
			} else {
				n2.setPrevious(tmp1);
			}
		}

		return true;
	}

	@Override
	public String toString() {

		String res = size + " Elements: ";

		int i = 0;
		for (CompleteEdge e = head; e != null; e = e.getNext(), i++) {

			res += i == 0 ? "" : ", ";
			if (e instanceof CompleteEdge) {
				res += "(" + ((CompleteEdge) e).getSource() + ","
						+ e.getTarget() + "," + e.getWeight() + ")";
			} else {
				res += "(" + e.getTarget() + "," + e.getWeight() + ")";
			}

		}

		return res;
	}

	// private void insertionSort(int fromIdx, int toIdx,
	// Comparator<CompleteEdge> comp) {
	// int range = toIdx - fromIdx;
	// if (range <= 1)
	// return;
	// CompleteEdge next = (CompleteEdge) get(fromIdx + 1);
	// CompleteEdge tmp1, tmp2, p, n;
	// int k;
	// for (int i = fromIdx + 1; i < toIdx; i++) {
	// tmp1 = next;
	// next = tmp1.getNext();
	// k = i;
	// while (k > fromIdx && comp.compare(tmp1, tmp1.getPrevious()) < 0) {
	// tmp2 = tmp1.getPrevious();
	// p = tmp2.getPrevious();
	// n = tmp1.getNext();
	// if (n != null) {
	// n.setPrevious(tmp2);
	// } else {
	// tail = tmp2;
	// }
	// if (p != null) {
	// p.setNext(tmp1);
	// } else {
	// head = tmp1;
	// }
	// tmp2.setNext(n);
	// tmp1.setPrevious(p);
	// tmp2.setPrevious(tmp1);
	// tmp1.setNext(tmp2);
	// k--;
	// }
	// }
	// }

	private void insertionSort(int fromIdx, int toIdx) {
		int range = toIdx - fromIdx;
		if (range <= 1)
			return;
		CompleteEdge next = get(fromIdx + 1);
		CompleteEdge tmp1, tmp2, p, n;
		int k;
		for (int i = fromIdx + 1; i < toIdx; i++) {
			tmp1 = next;
			next = tmp1.getNext();
			k = i;
			while (k > fromIdx && tmp1.compareTo(tmp1.getPrevious()) < 0) {
				tmp2 = tmp1.getPrevious();
				p = tmp2.getPrevious();
				n = tmp1.getNext();
				if (n != null) {
					n.setPrevious(tmp2);
				} else {
					tail = tmp2;
				}
				if (p != null) {
					p.setNext(tmp1);
				} else {
					head = tmp1;
				}
				tmp2.setNext(n);
				tmp1.setPrevious(p);
				tmp2.setPrevious(tmp1);
				tmp1.setNext(tmp2);
				k--;
			}
		}
	}

	private void arraySort(int fromIdx, int toIdx, Comparator<CompleteEdge> comp) {
		CompleteEdge[] tmp = toCompleteEdgeArray(fromIdx, toIdx);

		CompleteEdge next = null;
		if (toIdx < size)
			next = get(toIdx);

		CompleteEdge prev = null;
		if (fromIdx > 0)
			prev = get(fromIdx - 1);

		Arrays.sort(tmp, comp);
		for (int i = 0; i < tmp.length - 1; i++) {
			tmp[i].setNext(tmp[i + 1]);
			tmp[i + 1].setPrevious(tmp[i]);
		}

		if (fromIdx == 0) {
			head = tmp[0];
			head.setPrevious(null);
		} else {
			prev.setNext(tmp[0]);
			tmp[0].setPrevious(prev);
		}
		if (toIdx == size) {
			tail = tmp[tmp.length - 1];
			tail.setNext(null);
		} else {
			next.setPrevious(tmp[tmp.length - 1]);
			tmp[tmp.length - 1].setNext(next);
		}
	}

	private void arraySort(int fromIdx, int toIdx) {
		CompleteEdge[] tmp = toArray(fromIdx, toIdx);

		CompleteEdge next = null;
		if (toIdx < size)
			next = get(toIdx);

		CompleteEdge prev = null;
		if (fromIdx > 0)
			prev = get(fromIdx - 1);

		Arrays.sort(tmp);
		for (int i = 0; i < tmp.length - 1; i++) {
			tmp[i].setNext(tmp[i + 1]);
			tmp[i + 1].setPrevious(tmp[i]);
		}

		if (fromIdx == 0) {
			head = tmp[0];
			head.setPrevious(null);
		} else {
			prev.setNext(tmp[0]);
			tmp[0].setPrevious(prev);
		}
		if (toIdx == size) {
			tail = tmp[tmp.length - 1];
			tail.setNext(null);
		} else {
			next.setPrevious(tmp[tmp.length - 1]);
			tmp[tmp.length - 1].setNext(next);
		}
	}

	private CompleteEdge[] toCompleteEdgeArray(int fromIdx, int toIdx) {
		CompleteEdge[] res = new CompleteEdge[toIdx - fromIdx];
		CompleteEdge e = get(fromIdx);
		for (int i = 0; i < res.length; i++) {
			if (e instanceof CompleteEdge) {
				res[i] = (CompleteEdge) e;
			} else {
				throw new IllegalComponentStateException(
						"e not instance of CompleteEdge");
			}
			e = e.getNext();
		}
		return res;
	}

	private CompleteEdge[] toArray(int fromIdx, int toIdx) {
		CompleteEdge[] res = new CompleteEdge[toIdx - fromIdx];
		CompleteEdge e = get(fromIdx);
		for (int i = 0; i < res.length; i++) {
			res[i] = e;
			e = e.getNext();
		}
		return res;
	}

	@Override
	public Iterator<CompleteEdge> iterator() {
		return new EdgeIterator();
	}

	private class EdgeIterator implements Iterator<CompleteEdge> {

		private CompleteEdge currentEdge;

		private EdgeIterator() {
			currentEdge = head;
		}

		@Override
		public boolean hasNext() {
			return currentEdge != null;
		}

		@Override
		public CompleteEdge next() {
			CompleteEdge res = currentEdge;
			currentEdge = currentEdge.getNext();
			return res;
		}

		@Override
		public void remove() {
			System.out.println("remove is not implemented!");
		}

	}

}
